/**
 * 面试题 04.06. 后继者
 * https://leetcode.cn/problems/successor-lcci/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
function inorderSuccessor(root, p) {
  let cur = null;
  /**
   * @param {TreeNode} node
   * @return {boolean}
   */
  function dfs(node) {
    if (!node) {
      return false;
    }
    if (dfs(node.left)) {
      return true;
    }
    if (cur === p) {
      cur = node;
      return true;
    }
    cur = node;
    return dfs(node.right);
  }
  if (dfs(root)) {
    return cur;
  }
  return null;
}

let root;

root = createTreeNode([2, 1, 3]);
console.log(inorderSuccessor(root, root.left).val === 2);
root = createTreeNode([5, 3, 6, 2, 4, null, null, 1]);
console.log(inorderSuccessor(root, root.right) === null);
